package 刷题.Leedcode144;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

//迭代
//利用栈
public class Solution2 {
    public List<Integer> preorderTraversal(TreeNode root) {
        //创建一个顺序表
        List<Integer> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        //创建一个栈
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);//入栈
        //循环条件:栈不为空
        while (!stack.isEmpty()) {
            root = stack.pop();//出栈
            ret.add(root.val);//将结点元素入栈
            //这里先右后左，保证左子树先遍历
            //因为栈先入后出
            //所以先右后左，左边的元素就在最上面
            if (root.right != null) {
                stack.push(root.right);
            }
            if (root.left != null) {
                stack.push(root.left);
            }
        }
        return ret;
    }
}
